776. Roads

In Ukraine, as you know, a lot of problems. One of them – the road. The newly elected president of Ukraine decided to do road construction. His goal – to build some additional amount of roads between cities so that you can drive from any city of Ukraine in any (possibly through other cities, not necessarily directly). Naturally, any additional roads should be built as possible.

We assume that all the roads in Ukraine bilateral (and already available, and those that will be built), that is, it may move in both directions. Note that between the two cities may be somewhat expensive. In addition, there may be roads connecting the city to itself.

Input. The first line contains two natural numbers n and m (1 ≤ n, m ≤ 10000) – number of cities and the number of existing roads. The following m lines contain two integers a_i and b_i (1 ≤ a_i, b_i ≤ n) – the numbers of cities connected to an existing road.

Output. Print the minimum number of roads to be constructed, to exist a path from any city to any.

Sample input	Sample output
7 5 1 3 2 3 3 2 2 4 6 7	2

SOLUTION

graphs – depth first search

Algorithm analysis

Since the graph contains 10000 vertices, we’ll use an adjacency list to store it. Using the input list of edges, construct an adjacency list. Find the number of connected components using depth-first search. The number of new roads to be built is equal to the number of connected components minus 1.

Example

Graph shown in the sample looks like this:

Graph contains 3 connected components. To connect them, it is enough to add 2 edges.

Algorithm realization

Declare an adjacency list and an array used, where we mark the visited vertices.

vector<vector<int> > g;

vector<int> used;

Function dfs runs depth first search from the vertex v.

void dfs(int v)

{

used[v] = 1;

for (int i = 0; i < g[v].size(); i++)

{

int to = g[v][i];

if (!used[to]) dfs(to);

}

}

The main part of the program. Read the input data.

scanf("%d %d", &n, &m);

g.resize(n + 1);

Read the edges, construct the adjacency list of the graph.

for (i = 1; i <= m; i++)

{

scanf("%d %d", &a, &b);

g[a].push_back(b);

g[b].push_back(a);

}

Start the depth-first search on a disconnected graph, count the number of connected components in the cnt variable.

used.resize(n + 1);

cnt = 0;

for (i = 1; i <= n; i++)

if (used[i] == 0)

{

dfs(i);

cnt++;

}

Print the number of roads to be built.

printf("%d\n", cnt - 1);

Algorithm realization – disjoint sets

#include <stdio.h>

#define MAX 10001

int mas[MAX];

int Repr(int n)

{

while (n != mas[n]) n = mas[n];

return n;

}

void Union(int x, int y)

{

int x1 = Repr(x), y1 = Repr(y);

if (x1 == y1) return;

mas[x1] = y1;

}

int a, b, i, j, n, m, count;

int main(void)

{

scanf("%d %d", &n, &m);

for (i = 1; i <= n; i++) mas[i] = i;

for (i = 0; i < m; i++)

{

scanf("%d %d", &a, &b);

Union(a, b);

}

count = 0;

for (i = 1; i <= n; i++)

if (mas[i] == i) count++;

printf("%d\n", count - 1);

return 0;

}

Java realization

import java.util.*;

public class Main

{

static ArrayList<Integer>[] g;

static boolean used[];

static int n, m;

static void dfs(int v)

{

used[v] = true;

for(int i = 0; i < g[v].size(); i++)

{

int to = g[v].get(i);

if (used[to] == false) dfs(to);

}

}

@SuppressWarnings("unchecked")

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

n = con.nextInt();

m = con.nextInt();

used = new boolean[n+1];

g = new ArrayList[n+1];

for(int i = 0; i <= n; i++)

g[i] = new ArrayList<Integer>();

for (int i = 0; i < m; i++)

{

int a = con.nextInt();

int b = con.nextInt();

g[a].add(b);

g[b].add(a);

}

int cnt = 0;

for(int i = 1; i <= n; i++)

if (used[i] == false)

{

dfs(i);

cnt++;

}

System.out.println(cnt - 1);

con.close();

}

}